class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> ret;
        queue<TreeNode*> q;

        if(root)
            q.push(root);

        while(!q.empty())
        {
            vector<int> v;
            int levelsize = q.size();
            for(int i = 0; i < levelsize;i++)
            {
                TreeNode* front = q.front();
                q.pop();
                int val = front->val;
                v.push_back(front->val);
                if(front->left)
                    q.push(front->left);
                if(front->right)
                    q.push(front->right);
            }
            ret.push_back(v);
        }
        return ret;
    }
};

class MyStack {
public:
    queue<int> q1;
    queue<int> q2;
    
    MyStack() {

    }
    
    void push(int x) 
    {
        //直接往q2中插入数据
        //q1不为空就将q1数据一次插入q2
        //交换两个queue

        q2.push(x);

        while(!q1.empty())
        {
            q2.push(q1.front());
            q1.pop();
        }

        swap(q1,q2);

    }
    
    int pop() 
    {
        int tmp = q1.front();
        q1.pop();
        return tmp;
    }
    
    int top() {
        return q1.front();
    }
    
    bool empty() {
        return q1.empty();
    }
};
